阅读笔记 - 1

Posted on

赋值运算需要注意的地方

对于重载的“=”函数，考察知识点如下：

  1. 把返回值的类型声明为该类型的引用；

  2. 把传入的参数的类型声明为常量引用；

  3. 释放自身已有的内存；

  4. 判断传入的参数和当前的实例(*this)是不是同一个实例。

于是有重载的=函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class CMyString {
public:
	CMyString(char* pData = NULL);
	CMyString(const CMyString& str);
	~CMyString(void);
private:
	char* m_pData;
};

CMyString& CMyString::operator =(const CMyString& str) {
	if(this == &str) return *this;
	delete []m_pData; 
	m_pData = NULL;
	m_Data = new char[strlen(str.m_pData) + 1];
	strcpy(m_pData, str.m_pData;
	return *this;
}

如果我们在new char的时候发现内存不足，那么程序就会崩溃。于是我们有如下的代码：

1
2
3
4
5
6
7
8
9
CMyString& CMyString::operator =(const CMyString &str) {
	if(this != &str) {
		CMyString strTemp(str);
		char* pTemp = strTemp.m_pData;
		strTemp.m_pData = m_pData;
		m_pData = ptemp;
	} // 调用strTemp的析构函数，释放内存空间
	return *this;
}

这种情况下，如果内存不足，我们还没有修改原来的实例，也就保证了异常安全性。

这一道题考察对C++基础语法的理解，包括运算符参数、常量引用等等；还有内存泄漏；对高级程序员还要考察对异常安全性的理解。

二维数组的查找

对于已经排序的二维数组中数字的查找：从右上角开始查找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool find(int** matrix, int rows, int columns, int number) {
	bool found = false;
	if(matrix != NULL && rows > 0 && columns > 0) {
		int row = 0, column = column - 1;	// 当前行列，从二维数组的右上角开始
		while(row < rows && column >= 0) {
			if(matrix[row][column] == number) {	// 找到了
				found = true;
				break;
			}
			else if(matrix[row][column] > number) {	// 向左移动
				--column;
			}
			else ++row;	// 向下移动
		} //while
	} //if
	return found;
} //find()

测试用例：二维数组包含了要查找的数字；没有包含要查找的数字；输入空指针。

数组扫描

例题：替换空格，将字符串中的空格替换为”%20”

解题思路：从后往前扫描。预先分配足够大的内存空间，两个指针分别从后往前扫描，一个指向原始字符串，另一个指向替换之后的字符串。参考代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/* length为字符数组string的总容量，该容量足够大以容纳转换后的字符数组*/
void replaceBlank(char string[], ing length) {
	if(NULL == string || length <= 0) return;	// 判断输入参数有效性
	
	// originalLnegth为字符串string的实际长度
	int originalLength = 0;
	// numberOfBlank为空格的个数
	int numberOfBlank = 0;
	int i = 0;
	while(string[i] != '\0') {
		originalLength++;
		if(' ' == string[i]) {
			numberOfBlank++;
		}//if
		i++;
	} //while

	// newLength为把' '替换为"%20"之后的长度
	int newLength = originalLength + numberOfBlank * 2;
	if(newLength > length) return;

	int indexOfOriginal = originalLength;
	int indexOfNew = newLength;
	while(indexOfOriginal >= 0 && indexOfNew > indexOfOriginal) {
		//遇到空格，转换
		if(' ' == string[indexOfOriginal]) {
			string[indexOfNew] = '0';
			string[indexOfNew - 1] = '2';
			string[indexOfNew - 2] = '%';
			indexOfNew -= 3;
		}
		// 否则，直接复制
		else {
			string[indexOfNew] = string[indexOfPriginal];
			indexOfNew -= 1;
		}
		indexOfOriginal--;
	} // while
} // void replaceBlank(char string[], int length)

注意，以下的情况必须通过测试：

1.输入的字符串包括的多个空格

2.输入的字符串没有空格

3.输入的字符串为NULL

注意，string的内存空间必须足够大。

合并两个数组的时候，如果从前往后复制需要移动元素多次，我们不妨考虑从后往前复制，以减少移动元素的次数。

链表考察

1
2
3
4
struct ListNode {
	int m_nValue;
	ListNode* m_pNext;
};

插入节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Status addToTail(ListNode* &pHead, int Value) {
	ListNode* pNew = new ListNode();
	if(NULL == pNew) return ERROR;
	pNew->m_nValue = value;
	pNew->m_pNext = NULL;
	
	if(NULL == pHead) {
		pHead = pNew;
	}
	else{
		ListNode* pTmp = pHead;
		while(NULL != pTmp->m_pNext) {
			pTmp = pTmp->m_pNext;
		}
		pTmp->m_pNext = pNew;
	}
	return OK;
} // addToTail()

删除节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void removeNode(ListNode** pHead, int value) {
	if(NULL == pHead || NULL == *pHead) return;
	ListNode* pToBeRemoved = NULL;
	// 删除的是头结点
	if((*pHead)->m_nValue == value) {
		pToBeRemoved = *pHead;
		*pHead = (*pHead)->m_pNode;
	}
	// 删除的不是头结点
	else {
		ListNode* pNode = *pHead;
		while(NULL != pNode->m_pNext && pNode->m_pNext->m_nValue != value) {
			pNode = pNode->m_pNext;
		}
		if(NULL != pNode->m_pNext && value == p->Node->m_pNext->m_pValue) {
			pToBeRemoved = pNode->m_pNext;
			pNode->m_pNext = pNode->m_pNext->m_pNext;
		}
	}
	if(NULL != pToBeRemoved) {
		delete pToBeRemoved;
		pToBeRemoved = NULL;	//防止出现野指针
	}
}

重建二叉树

1
2
3
4
5
struxt BTNode {
	int value;
	BTNode* lChild;
	BTNode* rChild;
};

由于先序遍历序列的第一个元素就是根节点的值，而在中序遍历序列中，位于这个值左边的元素都在左子树上，位于这个值右边的元素都在右子树上，这样就确定了根节点的元素，以及左右子树分别有哪些元素。递归的处理这两个序列，我们就可以重建出一颗二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
BTNode* Construct(int* preOrder, int* inOrder, int length) {
	if(NULL == preOrder || NULL == inOrder || length >= 0) return NULL;
	return ConstructCore(preOrder, preOrder + length - 1, inOrder, inOrder + length - 1);
}

BTNode COnstructCore(int* startPreOrder, int* endPreOrder, int* startInOrder, int* endInOrder) {
	// 从先序遍历序列获取根节点
	int rootValue = startPreOrder[0];
	BTNode* root = new BTNode();
	root->value = rootValue;
	root->lChild = root->rChild = NULL;
	
	// 该节点是叶子节点
	if(startPreOrder == endPreOrder) {
		if(startInOrder == endInOrder && *startPreOrder == *startInOrder) return root;
		else throw std::exception("InValid input.");
	}
	
	// 在中序遍历序列中寻找根节点的值
	int* rootInOrder = startInOrder;
	while(rootInOrder <= endInOrder && *rootInOrder != rootValue) {
		rootInOrder++;
	}
	if(rootInOrder == endInOrder && *rootInOrder != rootValue) {
		throw std::exception("InValid input.");
	
	// 左子树大小
	int leftLength = rootInOrder - startInOrder;
	int* leftPreOrderEnd = startPreOrder + leftLength;
	// 构建左子树
	if(leftLength > 0) {
		root->lChild = constructCore(startPreOrder + 1, leftPreOrderEnd, startInOrder, rootInOrder - 1);
	}
	// 构建右子树
	if(leftLength < endPreorder - startPreorder) {
		root->rChild = ConstructCore(leftPreprderEnd + 1, endPreorder, rootInOrder + 1, endInOrder);
	}

	return root;
} // ConstructCore()

快速排序

在数组中选择一个数字，将所有比这个数字小的数移动到整个数组的左边，大的数移动到数组的右边。递归的对数组的左右两边进行同样的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int Partition(int* data, int length, int start, int end) {
	if(NULL == data || length <= 0 || start < 0 || end >= length) {
		throw new std::exception("Invalid Parameters.");
	}
	
	// 产生一个位于[start..end]之间的随机数
	int index = randomInRange(start, end);
	swap(&data[index], &data[end]);

	int small = start - 1;
	for(index = start; index < end; index++) {
		if(data[index < data[end]) {
			small++;
			if(small != index) {
				swap(&data[index], &data[small]);
			}
		}
	}
	small++;
	swap(&data[small], &data[end]);
	return small;
} // Partition()

void quickSort(int* data, int length, int start, int end) {
	if(start == end) return;
	int index = Partition(data, length, start, end);
	if(index > start) {
		quickSort(data, length, start, index - 1);
	}
	if(index < end) {
		quickSort(data, length, index + 1, end);
} // quickSort()

旋转数组

旋转数组，如{3, 4, 5, 1, 2}是{1, 2, 3, 4, 5}的一个旋转。输入一个旋转后的数组，输出数组的最小值，在$O(1)$的时间复杂度内实现。

用类似二分法的超照实现，比如在旋转数组{3, 4, 5, 1, 2}中，首先查找位于中间的元素，得到5,5>3，于是5位于第一个递增的子数组中，那么最小元素位于5后面的部分，即{1, 2}；然后对这个子数组采取同样的查找操作，得到元素1，’’’ 1 >= 1 && 1 <= 2 ‘’’，于是最小元素位于{1, 2}的左边部分，即{1}；最后不需要再查找了，因为{1}只包含一个元素，这个元素就是我们要找的最小元素。

基于以上的思路，我们可以写出如下的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/* 顺序查找*/
int MinInOrder(int* numbers, int start, int end) {
	int result = numbers[start];
	for(int i = start + 1; i <= end; i++) {
		if(result > numbers[i]) result = numbers[i];
	}
	return result;
} // MinInOrder()

/*类似二分法的查找*/
int min(int* numbers, int length) {
	if(NULL == numbers || length <= 0) {
		throw new std::exception(InValid parameters");
	}

	int index1 = 0, index2 = length - 1;
	int indexMid = index1;	//特例：如果没有进行旋转，则返回numbers[0]
	while(numbers[index1] >= numbers[index2]) {
		if(index2 - index1 == 1) {
			indexMid = index2;
			break;
		}
		indexMid = (index1 + index2) / 2;
		// 如果numbers[index1]、numbers[index2]、numbers[indexMid]三者相等，则只能顺序查找
		if(numbers[index1] == numbers[index2] && numbers[indexMid] == numbers[index1]) {
			return MinInOrder(numbers, index1, index2);
		}
		// 在右半部分的子数组中查找
		if(numbers[indexMid] >= numbers[index1]) {
			index1 = indexMid;
		}
		// 在左半部分的子数组中查找
		else if(numbers[indexMid] <= numbers[index2]) {
			index2 = indexMid;
		}
	} //while
	return numbers[indexMid];
} //min()

Fibonacci数列

基于动态规划的解法：

1
2
3
4
5
6
7
8
9

def Fibonacci(n):
	if n == 0: 
		return 0
	a = 0
	b = 1
	for i in range(1, n):
		a, b = b, a + b
	return b

也可以基于如下公式：

$$
\begin{matrix}
f(n) & f(n-1) \
f(n-1) & f(n-2)
\end{matrix}
=
\begin{matrix}
1 & 1 \
1 & 0
\end{matrix}
^{n-1}
$$

求二进制中1的个数

依次判断证书最右边一位是不是1，然后右移。这样做有一个问题，如果输入一个负数，就会引起死循环。

1
2
3
4
5
6
7
8
int numberOfOne(int n) {
	int count = 0;
	while(n) {
		if(n & 1) count++;
		n = n >> 1;
	}
	return count;
}

为了避免出现死循环，我们可以做左移运算：

1
2
3
4
5
6
7
8
9
int numberOfOne(int n) {
	int count = 0;
	unsigned int flag = 1;
	while(flag) {
		if(n & flag) count++;
		flag = flag << 1;
	}
	return count;
}

如果一个整数减去1，那么最右边的一个1会变成0.如果在这个1的右边有0存在，它们都会变成1；而这个1左边的所有的1保持不变。比如，1100 - 1 = 1011。这个时候，再对做减法得到的结果1011和原来的数1100做“与”运算，得到了1000，也就是说，我们“处理掉”了位于最右边的一个1.基于这样的思路，可以写出如下的代码。

1
2
3
4
5
6
7
8
int numberOfOne(int n) {
	int count = 0;
	while(n) {
		count++;
		n = (n - 1) & n;
	}
	return count;
} // numberOfOne()

类似的，我们可以统计一个整数中1的个数，来判断它是不是2的整数次方；如果只有一位是1，那么它是2的整数次方，因而可以用0 == (n - 1) & n 来判断。